#pragma once
// 排序练习 -20230215-

#include <iostream>
#include <stack>
#include <utility> 
#include <cstring>
#include <assert.h>

// 选择排序 -不稳定
template<class T>
void selectSort(T& seq, int len)
{
	int maxi, mini;
	for (int i = 0; i < len / 2; ++i)
	{
		maxi = mini = i;
		for (int j = i; j < len - i; ++j)
		{
			if (seq[maxi] < seq[j]) maxi = j;
			if (seq[mini] > seq[j]) mini = j;
		}
		std::swap(seq[mini], seq[i]);
		if (maxi == i) maxi = mini;
		std::swap(seq[maxi], seq[len - i - 1]);
	}
}

// 基本策略1
template<class T>
int _quickSort1(T& seq, int start, int end)
{
	int target = start;  // 目标值为此范围内第一个
	int left = start + 1, right = end;
	while (left < right)
	{
		// 右边找小，找小的先走，结束的时候右边此位置一定是小的（除开左指针一次没有动的情况）
		while (right > left && seq[right] >= seq[target])  // 注意此处的=符号，如果没有等于那么遇到相同数字序列的时候就会陷入死循环
			--right;
		while (left < right && seq[left] <= seq[target])  // 左边是找大的
			++left;
		if (left < right) std::swap(seq[left], seq[right]);
	}
	if (seq[right] < seq[target]) std::swap(seq[right], seq[target]);  // 如果左指针一次没动，说明此时找到的目标位置大小不确定，需要重新评估一次
	return right;
}

// 挖坑法2
template<class T>
int _quickSort2(T& seq, int start, int end)
{
	int target = seq[start];  // 目标值保存，此时此位置被视为坑位，等待填坑
	int left = start + 1, right = end;
	int pit = start;

	while (left < right)
	{
		// 同1，右边先找小
		while (right > left && seq[right] >= target)
			--right;
		// 存在两种情况：1.right!=left,此时一定找到小的了 2.right==left。->此时不一定是小，需要进行判断
		if (seq[right] < target)
		{
			seq[pit] = seq[right];  // 填坑
			pit = right;  // 转移坑
		}
		while (left < right && seq[left] <= target)
			++left;
		// 注意此时同样有两种情况：第一种left == right，如果上面right处理过此处填坑和转移都是移动自身，如果没有处理此时就不可填坑 第二种就是正常结束
		if (left != right)
		{
			seq[pit] = seq[left];  // 填坑
			pit = left;  // 转移坑
		}
	}
	seq[pit] = target;
	return pit;
}

// 双指针法3 -推荐好写-
template<class T>
int _quickSort3(T& seq, int start, int end)
{
	int target = start;
	int left = start, right = start + 1;
	// right每次都要走，往右找小，如果找到小了，需要和++left进行交换，最后right超出边界，left要么是交换后的小，要么就是本身。注意left只是在右找到小之后才++

	while (right <= end)
	{
		if (seq[right] < seq[target] && ++left != right)  // 避免本地交换
		{
			std::swap(seq[right], seq[left]);
		}
		++right;
	}
	std::swap(seq[target], seq[left]);
	return left;
}

// 优化-三数取中
template<class T>
void tripleNumberCenter(T& seq, int start, int end)
{
	int middle = (end - start) / 2 + start;
	if (seq[middle] > seq[start])
	{
		if (seq[middle] <= seq[end]) std::swap(seq[middle], seq[start]);
		else if (seq[end] > seq[start]) std::swap(seq[end], seq[start]);
	}
	else
	{
		if (seq[middle] > seq[end]) std::swap(seq[middle], seq[start]);
		else if (seq[end] <= seq[start]) std::swap(seq[end], seq[start]);
	}
}

// 选择排序 - 快速排序-不稳定
template<class T>
void quickSort(T& seq, int len)
{
	// 三种实现方案+非递归操作+三数取中优化方案
	int target = 0;
	std::stack<std::pair<int, int>> st;
	st.push(std::make_pair(target, len - 1));
	int flag = 1;
	while (!st.empty())
	{
		int left = st.top().first, right = st.top().second;
		st.pop();
		// 优化 - 目标参数传入的时候时候会认定此范围第一个需要排序，那么对第一个如果是中间的数 - 接近二分
		//tripleNumberCenter(seq, left, right);
		target = _quickSort1(seq, left, right);
		//target = _quickSort2(seq, left, right);
		//target = _quickSort3(seq, left, right);
		if (flag)
		{
			for (auto a : seq) std::cout << a << " ";
			std::cout << std::endl;
			flag = 0;
		}
		if (target - 1 > left) st.push(std::make_pair(left, target - 1));
		if (target + 1 < right) st.push(std::make_pair(target + 1, right));
	}
}

//快速排序：hoare版本(递归版本)
void QuickSort(int* a, int head, int end)
{
	//结束标志
	if (head >= end)
		return;
	assert(a);

	int target = head;
	int left = target + 1;
	int right = end;

	while (right > left)
	{
		//右边先找，找到比target处的数字小的停下   下面经过画图分析，如果不加等号的话，就会陷入死循环~
		while (right > left && a[right] >= a[target])
		{
			right--;
		}

		while (right > left && a[left] <= a[target])
		{
			left++;
		}

		if (right > left)
			std::swap(a[right], a[left]);
	}
	if (a[right] < a[target])//防止传入的两个数，一次也不进入循环，然后无法判断和target位置所在数组元素大小的情况
		std::swap(a[target], a[right]);
	target = right;

	//进入递归，分而治之的思想
	//左边
	QuickSort(a, head, target - 1);
	//右边
	QuickSort(a, target + 1, end);

}

// 插入排序
template<class T>
void insertSort(T& seq, int len)
{
	for (int i = 1; i < len; ++i)
	{
		int exc = i;
		int tmp = seq[exc];
		while (exc > 0 && tmp < seq[exc - 1])
		{
			seq[exc] = seq[exc - 1];
			--exc;
		}
		seq[exc] = tmp;
	}
}

// 归并排序 - 递归版本
template<class T>
void mergeSort(T& seq, int begin, int end)
{
	if (begin >= end) return;
	int middle = (end - begin) / 2 + begin;
	mergeSort(seq, begin, middle);
	mergeSort(seq, middle + 1, end);
	// 此时认为两边均为有序的，我们在进行归并排序
	int left = begin, right = middle + 1;
	int* arr = new int[end - begin + 1];  // 此处可以进行优化，不让其频繁的在函数内部开辟和释放堆空间，只需要外部申请和释放一次即可和seq一致。
	int i = 0;

	while (left <= middle && right <= end)
	{
		if (seq[left] < seq[right]) arr[i++] = seq[left++];
		else arr[i++] = seq[right++];
	}
	while (left <= middle)
	{
		arr[i++] = seq[left++];
	}
	while (right <= end)
	{
		arr[i++] = seq[right++];
	}
	memcpy(seq + begin, arr, sizeof(int) * (end - begin + 1));
	delete[] arr;
}

// 归并排序-非递归版本
template<class T>
void mergeSort2(T& seq, int len)
{
	int gap = 1;
	int* arr = new int[len];
	while (gap < len)  // 模拟递归过程
	{
		for (int i = 0; i < len; i += 2 * gap)  // 两组两组进行合并 然后把一轮分组合并完
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			// 修正边界
			if (end1 >= len || begin2 >= len) break;
			if (end2 >= len) end2 = len - 1;

			int left = begin1, right = begin2;
			int n = begin1;
			while (left <= end1 && right <= end2)
			{
				if (seq[left] < seq[right]) arr[n++] = seq[left++];
				else arr[n++] = seq[right++];
			}
			while (left <= end1)
			{
				arr[n++] = seq[left++];
			}
			while (right <= end2)
			{
				arr[n++] = seq[right++];
			}

			memcpy(seq + i, arr + i, sizeof(int) * gap * 2);
		}
		gap *= 2;
	}
	delete[] arr;
}

template<class T>
void mySort(T& seq)
{
	int len = sizeof(seq) / sizeof(seq[0]);
	//selectSort(seq, len);  // 选择排序
	//quickSort(seq, len);  // 快速排序
	//insertSort(seq, len);  // 插入排序
	//mergeSort(seq, 0, len - 1);  // 递归-归并排序
	mergeSort2(seq, len);  // 非递归-归并排序
}